<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="imlgw,半岛铁盒,blog,Java博客,程序员,个人博客,java開發,程序員,個人博客,Java">
    <meta name="description" content="大悲无泪，大悟无言，大笑无声。">
    <meta name="author" content="Resolmi">
    
    <title>
        
            字典树初探 |
        
        Tadow
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico">
    <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/css/font-awesome.min.css">
    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"imlgw.top","root":"/","language":"zh-CN","path":"search.json"};
    KEEP.theme_config = {"toc":{"enable":true,"number":true,"expand_all":true,"init_open":true},"style":{"primary_color":"#0066CC","avatar":"https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png","favicon":"https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":true},"first_screen":{"enable":true,"background_img":"/images/image.svg","description":"Keep It Simple & Stupid."},"scroll":{"progress_bar":{"enable":true},"percent":{"enable":true}}},"local_search":{"enable":true,"preload":false},"code_copy":{"enable":true,"style":"default"},"pjax":{"enable":true},"lazyload":{"enable":true},"version":"3.4.3"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 5.4.0"><link rel="stylesheet" href="/css/prism.css" type="text/css"></head>


<body>
<div class="progress-bar-container">
    
        <span class="scroll-progress-bar"></span>
    

    
        <span class="pjax-progress-bar"></span>
        <span class="pjax-progress-icon">
            <i class="fas fa-circle-notch fa-spin"></i>
        </span>
    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                Tadow
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/sbe"
                            >
                                订阅
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/links"
                            >
                                友链
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/about"
                            >
                                关于
                            </a>
                        </li>
                    
                    
                        <li class="menu-item search search-popup-trigger">
                            <i class="fas fa-search"></i>
                        </li>
                    
                </ul>
            </div>
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fas fa-search"></i></div>
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/sbe">订阅</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/links">友链</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/about">关于</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">字典树初探</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">Resolmi</span>
                        
                            <span class="author-label">BOSS</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;2019-12-17 00:00:00
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>&nbsp;
                    </li>
                
                    <li>
                        | <a href="/tags/%E6%A0%91/">树</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
        <span class="article-wordcount article-meta-item">
            <i class="fas fa-file-word"></i>&nbsp;<span>2.7k 字</span>
        </span>
    
    
        <span class="article-min2read article-meta-item">
            <i class="fas fa-clock"></i>&nbsp;<span>13 分钟</span>
        </span>
    
    
        <span class="article-pv article-meta-item">
            <i class="fas fa-eye"></i>&nbsp;<span id="busuanzi_value_page_pv"></span>
        </span>
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <h2 id="字典树"><a href="#字典树" class="headerlink" title="字典树"></a>字典树</h2><p>在计算机科学中，<strong>trie</strong>，又称<strong>前缀树</strong>或<strong>字典树</strong>，字典树设计的核心思想是空间换时间，所以数据结构本身比较消耗空间。但它利用了字符串的<strong>共同前缀（Common Prefix）</strong>作为存储依据，以此来节省存储空间，并加速搜索时间。Trie 的字符串搜索时间复杂度为 **O(m)**，m 为最长的字符串的长度，其查询性能与集合中的字符串的数量无关。其在搜索字符串时表现出的高效，使得特别适用于构建文本搜索和词频统计等应用</p>
<h3 id="性质"><a href="#性质" class="headerlink" title="性质"></a>性质</h3><p>与二分搜索树不同，<strong>键不是直接保存在节点中，而是由节点在树中的位置决定</strong>。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有<strong>叶子节点</strong>和部分内部节点所对应的键才有相关的值</p>
<h2 id="实现"><a href="#实现" class="headerlink" title="实现"></a>实现</h2><h3 id="使用TreeMap实现"><a href="#使用TreeMap实现" class="headerlink" title="使用TreeMap实现"></a>使用TreeMap实现</h3><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.*;</span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Trie</span></span>&#123;</span><br><span class="line">    <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span></span>&#123;</span><br><span class="line">        <span class="keyword">public</span> <span class="keyword">boolean</span> isWord; <span class="comment">//是否是一个完整单词</span></span><br><span class="line">        <span class="keyword">public</span> TreeMap&lt;Character,Node&gt; next;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(<span class="keyword">boolean</span> isWord)</span></span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.isWord = isWord;</span><br><span class="line">            next = <span class="keyword">new</span> TreeMap&lt;&gt;();</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">()</span></span>&#123;</span><br><span class="line">            <span class="keyword">this</span>(<span class="keyword">false</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> Node root;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> size;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Trie</span><span class="params">()</span></span>&#123;</span><br><span class="line">        root=<span class="keyword">new</span> Node();</span><br><span class="line">        size=<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getSize</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> size;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//向Trie中添加word</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">addLoop</span><span class="params">(String word)</span></span>&#123;</span><br><span class="line">        Node cur=root;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;word.length();i++) &#123;</span><br><span class="line">            <span class="keyword">char</span> c=word.charAt(i);</span><br><span class="line">            <span class="keyword">if</span> (cur.next.get(c)==<span class="keyword">null</span>) &#123;</span><br><span class="line">                cur.next.put(c,<span class="keyword">new</span> Node());</span><br><span class="line">            &#125;</span><br><span class="line">            cur=cur.next.get(c);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (!cur.isWord) &#123;</span><br><span class="line">            size++;</span><br><span class="line">            cur.isWord=<span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//递归的添加</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">add</span><span class="params">(String word)</span></span>&#123;</span><br><span class="line">        add(root,word,<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">add</span><span class="params">(Node cur,String word,<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (index==word.length()) &#123;</span><br><span class="line">            <span class="keyword">if</span> (!cur.isWord) &#123;</span><br><span class="line">                size++;</span><br><span class="line">                cur.isWord=<span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">char</span> c=word.charAt(index);</span><br><span class="line">        <span class="keyword">if</span> (cur.next.get(c)==<span class="keyword">null</span>) &#123;</span><br><span class="line">            cur.next.put(c,<span class="keyword">new</span> Node());</span><br><span class="line">        &#125;</span><br><span class="line">        add(cur.next.get(c),word,index+<span class="number">1</span>); <span class="comment">//尾递归</span></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//查询word是否在Trie中</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">contains</span><span class="params">(String word)</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> contains(root,word,<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">contains</span><span class="params">(Node cur,String word,<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (index==word.length()) &#123;</span><br><span class="line">            <span class="keyword">return</span> cur.isWord;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">char</span> c=word.charAt(index);</span><br><span class="line">        <span class="keyword">return</span> cur.next.containsKey(c) &amp;&amp; contains(cur.next.get(c),word,index+<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//循环</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">containsLoop</span><span class="params">(String word)</span></span>&#123;</span><br><span class="line">        Node cur=root;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;word.length();i++) &#123;</span><br><span class="line">            Character c=word.charAt(i);</span><br><span class="line">            <span class="keyword">if</span> (!cur.next.containsKey(c)) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;   </span><br><span class="line">            &#125;</span><br><span class="line">            cur=cur.next.get(c);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> cur.isWord;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//是否有某个前缀</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">hasPerfix</span><span class="params">(String perfix)</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> hasPerfix(root,perfix,<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">hasPerfix</span><span class="params">(Node cur,String perfix,<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (index==perfix.length()) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">char</span> c=perfix.charAt(index);</span><br><span class="line">        <span class="keyword">return</span> cur.next.containsKey(c) &amp;&amp; hasPerfix(cur.next.get(c),perfix,index+<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//懒得写循环了。。。</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>整体上来说其实很简单，这里用的是TreeMap来存储当前节点的下一层节点，可以看到，在Node中并没有直接存储某个字符，而是对应了TreeMap的Key，但是由于TreeMap底层是红黑树，其实在数据量比较小的时候并没有优势，所以在某些情况下，我们也可以直接使用数组来存储节点，比如下面这道题</p>
<h2 id="LeetCode练手例题"><a href="#LeetCode练手例题" class="headerlink" title="LeetCode练手例题"></a>LeetCode练手例题</h2><h3 id="208-实现-Trie-前缀树"><a href="#208-实现-Trie-前缀树" class="headerlink" title="208. 实现 Trie (前缀树)"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/implement-trie-prefix-tree/" >208. 实现 Trie (前缀树)<i class="fas fa-external-link-alt"></i></a></h3><p>实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。</p>
<p><strong>示例:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">Trie trie = <span class="keyword">new</span> Trie();</span><br><span class="line"></span><br><span class="line">trie.insert(<span class="string">&quot;apple&quot;</span>);</span><br><span class="line">trie.search(<span class="string">&quot;apple&quot;</span>);   <span class="comment">// 返回 true</span></span><br><span class="line">trie.search(<span class="string">&quot;app&quot;</span>);     <span class="comment">// 返回 false</span></span><br><span class="line">trie.startsWith(<span class="string">&quot;app&quot;</span>); <span class="comment">// 返回 true</span></span><br><span class="line">trie.insert(<span class="string">&quot;app&quot;</span>);   </span><br><span class="line">trie.search(<span class="string">&quot;app&quot;</span>);     <span class="comment">// 返回 true</span></span><br></pre></td></tr></table></figure>

<p><strong>说明:</strong></p>
<ul>
<li>你可以假设所有的输入都是由小写字母 a-z 构成的。</li>
<li>保证所有输入均为非空字符串</li>
</ul>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Trie</span> </span>&#123;</span><br><span class="line">    <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span></span>&#123;</span><br><span class="line">        <span class="keyword">public</span> <span class="keyword">boolean</span> isWord; <span class="comment">//是否是一个完整单词</span></span><br><span class="line">        <span class="keyword">public</span> Node[] next;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(<span class="keyword">boolean</span> isWord)</span></span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.isWord = isWord;</span><br><span class="line">            next = <span class="keyword">new</span> Node[<span class="number">26</span>];</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">()</span></span>&#123;</span><br><span class="line">            <span class="keyword">this</span>(<span class="keyword">false</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> Node root;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/** Initialize your data structure here. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Trie</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        root=<span class="keyword">new</span> Node();</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Inserts a word into the trie. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">insert</span><span class="params">(String word)</span> </span>&#123;</span><br><span class="line">        insert(root,word,<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">insert</span><span class="params">(Node cur,String word,<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (index==word.length()) &#123;</span><br><span class="line">            <span class="keyword">if</span> (!cur.isWord) &#123;</span><br><span class="line">                cur.isWord=<span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">char</span> c=word.charAt(index);</span><br><span class="line">        <span class="keyword">if</span> (cur.next[c-<span class="string">&#x27;a&#x27;</span>]==<span class="keyword">null</span>) &#123;</span><br><span class="line">            cur.next[c-<span class="string">&#x27;a&#x27;</span>]=<span class="keyword">new</span> Node();</span><br><span class="line">        &#125;</span><br><span class="line">        insert(cur.next[c-<span class="string">&#x27;a&#x27;</span>],word,index+<span class="number">1</span>); <span class="comment">//尾递归</span></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/** Returns if the word is in the trie. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">search</span><span class="params">(String word)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> search(root,word,<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">search</span><span class="params">(Node cur,String word,<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (index==word.length()) &#123;</span><br><span class="line">            <span class="keyword">return</span> cur.isWord;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">char</span> c=word.charAt(index);</span><br><span class="line">        <span class="keyword">return</span> cur.next[c-<span class="string">&#x27;a&#x27;</span>]!=<span class="keyword">null</span>&amp;&amp; search(cur.next[c-<span class="string">&#x27;a&#x27;</span>],word,index+<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">/** Returns if there is any word in the trie that starts with the given prefix. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">startsWith</span><span class="params">(String prefix)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> startsWith(root,prefix,<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">startsWith</span><span class="params">(Node cur,String prefix,<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (index==prefix.length()) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">char</span> c=prefix.charAt(index);</span><br><span class="line">        <span class="keyword">return</span> cur.next[c-<span class="string">&#x27;a&#x27;</span>]!=<span class="keyword">null</span> &amp;&amp; startsWith(cur.next[c-<span class="string">&#x27;a&#x27;</span>],prefix,index+<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Your Trie object will be instantiated and called as such:</span></span><br><span class="line"><span class="comment"> * Trie obj = new Trie();</span></span><br><span class="line"><span class="comment"> * obj.insert(word);</span></span><br><span class="line"><span class="comment"> * boolean param_2 = obj.search(word);</span></span><br><span class="line"><span class="comment"> * boolean param_3 = obj.startsWith(prefix);</span></span><br><span class="line"><span class="comment"> */</span></span><br></pre></td></tr></table></figure>

<p>这里题目说明了所有的输入都是小写字符，所以可以直接使用固定大小的Node数组来实现，相比于上面的TreeMap时间空间上都会有很大的提升</p>
<h3 id="211-添加与搜索单词-数据结构设计"><a href="#211-添加与搜索单词-数据结构设计" class="headerlink" title="211. 添加与搜索单词 - 数据结构设计"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/add-and-search-word-data-structure-design/" >211. 添加与搜索单词 - 数据结构设计<i class="fas fa-external-link-alt"></i></a></h3><p>设计一个支持以下两种操作的数据结构：</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">addWord</span><span class="params">(word)</span></span></span><br><span class="line"><span class="function">bool <span class="title">search</span><span class="params">(word)</span></span></span><br></pre></td></tr></table></figure>

<p><code>search(word)</code> 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 <code>.</code> 可以表示任何一个字母。</p>
<p><strong>示例:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">addWord(<span class="string">&quot;bad&quot;</span>)</span><br><span class="line">addWord(<span class="string">&quot;dad&quot;</span>)</span><br><span class="line">addWord(<span class="string">&quot;mad&quot;</span>)</span><br><span class="line">search(<span class="string">&quot;pad&quot;</span>) -&gt; <span class="function"><span class="keyword">false</span></span></span><br><span class="line"><span class="function"><span class="title">search</span><span class="params">(<span class="string">&quot;bad&quot;</span>)</span> -&gt; <span class="keyword">true</span></span></span><br><span class="line"><span class="function"><span class="title">search</span><span class="params">(<span class="string">&quot;.ad&quot;</span>)</span> -&gt; <span class="keyword">true</span></span></span><br><span class="line"><span class="function"><span class="title">search</span><span class="params">(<span class="string">&quot;b..&quot;</span>)</span> -&gt; <span class="keyword">true</span></span></span><br></pre></td></tr></table></figure>


<p><strong>说明:</strong></p>
<p>你可以假设所有单词都是由小写字母 <code>a-z</code> 组成的。</p>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span></span>&#123;</span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">boolean</span> isWord; <span class="comment">//是否找到了一个单词</span></span><br><span class="line">    <span class="keyword">public</span> Node[] next;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(<span class="keyword">boolean</span> isWord)</span></span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.isWord = isWord;</span><br><span class="line">        next = <span class="keyword">new</span> Node[<span class="number">26</span>];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">this</span>(<span class="keyword">false</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span> Node root;</span><br><span class="line"></span><br><span class="line"><span class="comment">/** Initialize your data structure here. */</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="title">WordDictionary</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    root=<span class="keyword">new</span> Node();</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/** Adds a word into the data structure. */</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">addWord</span><span class="params">(String word)</span> </span>&#123;</span><br><span class="line">    addWord(root,word,<span class="number">0</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">addWord</span><span class="params">(Node cur,String word,<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (index == word.length()) &#123;</span><br><span class="line">        cur.isWord=<span class="keyword">true</span>;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">char</span> c=word.charAt(index);</span><br><span class="line">    <span class="keyword">if</span> (cur.next[c-<span class="string">&#x27;a&#x27;</span>]==<span class="keyword">null</span>) &#123;</span><br><span class="line">        cur.next[c-<span class="string">&#x27;a&#x27;</span>]= <span class="keyword">new</span> Node();</span><br><span class="line">    &#125;</span><br><span class="line">    addWord(cur.next[c-<span class="string">&#x27;a&#x27;</span>],word,index+<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/** Returns if the word is in the data structure. A word could contain the dot character &#x27;.&#x27; to represent any one letter. */</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">search</span><span class="params">(String word)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">return</span> search(root,word,<span class="number">0</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">search</span><span class="params">(Node cur,String word,<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (index == word.length()) &#123;</span><br><span class="line">        <span class="keyword">return</span> cur.isWord;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">char</span> c=word.charAt(index);</span><br><span class="line">    <span class="keyword">if</span> (c==<span class="string">&#x27;.&#x27;</span>) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;cur.next.length;i++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(cur.next[i]!=<span class="keyword">null</span> &amp;&amp; search(cur.next[i],word,index+<span class="number">1</span>))&#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> cur.next[c-<span class="string">&#x27;a&#x27;</span>]!=<span class="keyword">null</span> &amp;&amp; search(cur.next[c-<span class="string">&#x27;a&#x27;</span>],word,index+<span class="number">1</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>没啥好说的，遇到点就循环判断每个子节点就ok</p>
<h3 id="677-键值映射"><a href="#677-键值映射" class="headerlink" title="677. 键值映射"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/map-sum-pairs/" >677. 键值映射<i class="fas fa-external-link-alt"></i></a></h3><p>实现一个 MapSum 类里的两个方法，<code>insert</code> 和 <code>sum</code>。</p>
<p>对于方法 <code>insert</code>，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。</p>
<p>对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: insert(<span class="string">&quot;apple&quot;</span>, <span class="number">3</span>), 输出: Null</span><br><span class="line">输入: sum(<span class="string">&quot;ap&quot;</span>), 输出: <span class="number">3</span></span><br><span class="line">输入: insert(<span class="string">&quot;app&quot;</span>, <span class="number">2</span>), 输出: Null</span><br><span class="line">输入: sum(<span class="string">&quot;ap&quot;</span>), 输出: <span class="number">5</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>有了前面的铺垫，其实这个也很简单</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">MapSum</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span></span>&#123;</span><br><span class="line">        <span class="keyword">public</span> <span class="keyword">boolean</span> isWord; <span class="comment">//是否找到了一个单词</span></span><br><span class="line">        <span class="keyword">public</span> Node[] next;</span><br><span class="line">        <span class="keyword">public</span> <span class="keyword">int</span> value;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(<span class="keyword">boolean</span> isWord,<span class="keyword">int</span> value)</span></span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.isWord = isWord;</span><br><span class="line">            <span class="keyword">this</span>.value=value;</span><br><span class="line">            next = <span class="keyword">new</span> Node[<span class="number">26</span>];</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(<span class="keyword">int</span> value)</span></span>&#123;</span><br><span class="line">            <span class="keyword">this</span>(<span class="keyword">false</span>,value);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">private</span> Node root;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">MapSum</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        root=<span class="keyword">new</span> Node(<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">insert</span><span class="params">(String key, <span class="keyword">int</span> val)</span> </span>&#123;</span><br><span class="line">        insert(root,key,val,<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//a p p l e</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">insert</span><span class="params">(Node cur,String key, <span class="keyword">int</span> val,<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (index==key.length()) &#123;</span><br><span class="line">            cur.isWord=<span class="keyword">true</span>;</span><br><span class="line">            cur.value=val;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">char</span> c=key.charAt(index);</span><br><span class="line">        <span class="keyword">if</span> (cur.next[c-<span class="string">&#x27;a&#x27;</span>]==<span class="keyword">null</span>) &#123;</span><br><span class="line">            cur.next[c-<span class="string">&#x27;a&#x27;</span>]=<span class="keyword">new</span> Node(<span class="number">0</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        insert(cur.next[c-<span class="string">&#x27;a&#x27;</span>],key,val,index+<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">sum</span><span class="params">(String prefix)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> sum(root,prefix,<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">sum</span><span class="params">(Node cur,String prefix,<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (index == prefix.length()) &#123;</span><br><span class="line">            <span class="keyword">return</span> tireSum(cur);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">char</span> c=prefix.charAt(index);</span><br><span class="line">        <span class="keyword">if</span> (cur.next[c-<span class="string">&#x27;a&#x27;</span>]==<span class="keyword">null</span>) &#123;</span><br><span class="line">        	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> sum(cur.next[c-<span class="string">&#x27;a&#x27;</span>],prefix,index+<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">tireSum</span><span class="params">(Node cur)</span></span>&#123;</span><br><span class="line">    	<span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">    	<span class="keyword">if</span> (cur.isWord) &#123;</span><br><span class="line">    		sum+=cur.value;</span><br><span class="line">    	&#125;</span><br><span class="line">    	<span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;<span class="number">26</span>;i++) &#123;</span><br><span class="line">    		sum+=cur.next[i]!=<span class="keyword">null</span>?tireSum(cur.next[i]):<span class="number">0</span>;</span><br><span class="line">    	&#125;</span><br><span class="line">    	<span class="keyword">return</span> sum;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>还是和上面一样，利用前缀树，不过要在上面的基础上做一些改动添加一个value字段用来保存值，先在树中找到要求的前缀的最后一个单词所在的节点，然后就直接求这个节点所有的子节点中isWord的单词的value累加和就ok了，我上面的实现并不好，都是写的递归，而且是尾递归，很鸡肋其实</p>
<h3 id="820-单词的压缩编码"><a href="#820-单词的压缩编码" class="headerlink" title="820. 单词的压缩编码"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/short-encoding-of-words/" >820. 单词的压缩编码<i class="fas fa-external-link-alt"></i></a></h3><p>给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。</p>
<p>例如，如果这个列表是 <code>[&quot;time&quot;, &quot;me&quot;, &quot;bell&quot;]</code>，我们就可以将其表示为 S = <code>&quot;time#bell#&quot;</code> 和 <code>indexes = [0, 2, 5]</code>。</p>
<p>对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 “#” 结束，来恢复我们之前的单词列表。</p>
<p>那么成功对给定单词列表进行编码的最小字符串长度是多少呢？</p>
<p><strong>示例：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: words = [<span class="string">&quot;time&quot;</span>, <span class="string">&quot;me&quot;</span>, <span class="string">&quot;bell&quot;</span>]</span><br><span class="line">输出: <span class="number">10</span></span><br><span class="line">说明: S = <span class="string">&quot;time#bell#&quot;</span> ， indexes = [<span class="number">0</span>, <span class="number">2</span>, <span class="number">5</span>] 。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= words.length &lt;= 2000</code></li>
<li><code>1 &lt;= words[i].length &lt;= 7</code></li>
<li>每个单词都是小写字母 。</li>
</ul>
<p><strong>解法一</strong></p>
<p><code>2020.3.28</code> 打卡题，简单写了个Trie，纠结了半天要不要排序</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span> Node root;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">minimumLengthEncoding</span><span class="params">(String[] words)</span> </span>&#123;</span><br><span class="line">    root=<span class="keyword">new</span> Node();</span><br><span class="line">    <span class="comment">//纠结了半天要不要排序</span></span><br><span class="line">    Arrays.sort(words,(a,b)-&gt;b.length()-a.length());</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;words.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span>(!hasPrefix(words[i]))&#123;</span><br><span class="line">            add(words[i]);</span><br><span class="line">            res+=(words[i].length()+<span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span></span>&#123;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">public</span> Node[] next;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">()</span></span>&#123;</span><br><span class="line">        next = <span class="keyword">new</span> Node[<span class="number">26</span>];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//递归的添加</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">add</span><span class="params">(String word)</span></span>&#123;</span><br><span class="line">    <span class="comment">//后缀树</span></span><br><span class="line">    add(root,word,word.length()-<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">add</span><span class="params">(Node cur,String word,<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (index==-<span class="number">1</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">char</span> c=word.charAt(index);</span><br><span class="line">    <span class="keyword">if</span> (cur.next[c-<span class="string">&#x27;a&#x27;</span>]==<span class="keyword">null</span>) &#123;</span><br><span class="line">        cur.next[c-<span class="string">&#x27;a&#x27;</span>]=<span class="keyword">new</span> Node();</span><br><span class="line">    &#125;</span><br><span class="line">    add(cur.next[c-<span class="string">&#x27;a&#x27;</span>],word,index-<span class="number">1</span>); <span class="comment">//尾递归</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">hasPrefix</span><span class="params">(String word)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> hasPrefix(root,word,word.length()-<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">hasPrefix</span><span class="params">(Node cur,String word,<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(index==-<span class="number">1</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">char</span> c=word.charAt(index);</span><br><span class="line">    <span class="keyword">return</span> cur.next[c-<span class="string">&#x27;a&#x27;</span>]!=<span class="keyword">null</span> &amp;&amp; hasPrefix(cur.next[c-<span class="string">&#x27;a&#x27;</span>],word,index-<span class="number">1</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>解法二</strong></p>
<p>直接<strong>逆序</strong>后按<strong>字典序</strong>排序，这样单词的前缀包含关系就排好了，比如 time , me, bell, 最后就会变为 em emit lleb</p>
<p>然后遍历所有单词，如果前面的单词是后面的前缀，就把前面的单词丢掉，否则就需要加上当前字符长度，代码后面有时间再补</p>

        </div>

        
            <div class="post-copyright-info">
                <div class="article-copyright-info-container">
    <ul>
        <li>本文标题：字典树初探</li>
        <li>本文作者：Resolmi</li>
        <li>创建时间：2019-12-17 00:00:00</li>
        <li>
            本文链接：https://imlgw.top/2019/12/17/21e3bd45/
        </li>
        <li>
            版权声明：本博客所有文章除特别声明外，均采用 <a class="license" target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">BY-NC-SA</a> 许可协议。转载请注明出处！
        </li>
    </ul>
</div>

            </div>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2019/12/23/d1fa72ec/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">常用的一些工具和网站</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2019/12/09/44ba5333/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">线段树初探</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
            <div class="comment-container">
                <div class="comments-container">
    <div id="comment-anchor"></div>
    <div class="comment-area-title">
        <i class="fas fa-comments">&nbsp;评论</i>
    </div>
    

        
            <section class="disqus-comments">
<div id="disqus_thread">
  <noscript>Please enable JavaScript to view the <a target="_blank" rel="noopener" href="//disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
</section>

<script>
var disqus_shortname = 'imlgw';

var disqus_url = 'https://imlgw.top/2019/12/17/21e3bd45/';

(function(){
  var dsq = document.createElement('script');
  dsq.type = 'text/javascript';
  dsq.async = true;
  dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
  (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>

<script id="dsq-count-scr" src="//imlgw.disqus.com/count.js" async></script>
        
    
</div>

            </div>
        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2018</span>&nbsp;-&nbsp;
            
            2021&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">Resolmi</a>
        </div>
        
            <script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
            <div class="website-count info-item">
                
                    <span id="busuanzi_container_site_uv">
                        访问人数&nbsp;<span id="busuanzi_value_site_uv"></span>&ensp;
                    </span>
                
                
                    <span id="busuanzi_container_site_pv">
                        总访问量&nbsp;<span id="busuanzi_value_site_pv"></span>
                    </span>
                
            </div>
        
        
            <div class="icp-info info-item"><a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn">鄂ICP备18011208号</a></div>
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        
            <li class="tools-item page-aside-toggle">
                <i class="fas fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
            <li class="go-comment">
                <i class="fas fa-comment"></i>
            </li>
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="arrow-up fas fa-arrow-up"></i>
                <span class="percent"></span>
            </li>
        
    </ul>
</div>

    </div>

    
        <aside class="page-aside">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%AD%97%E5%85%B8%E6%A0%91"><span class="nav-number">1.</span> <span class="nav-text">字典树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%80%A7%E8%B4%A8"><span class="nav-number">1.1.</span> <span class="nav-text">性质</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%AE%9E%E7%8E%B0"><span class="nav-number">2.</span> <span class="nav-text">实现</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BD%BF%E7%94%A8TreeMap%E5%AE%9E%E7%8E%B0"><span class="nav-number">2.1.</span> <span class="nav-text">使用TreeMap实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#LeetCode%E7%BB%83%E6%89%8B%E4%BE%8B%E9%A2%98"><span class="nav-number">3.</span> <span class="nav-text">LeetCode练手例题</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#208-%E5%AE%9E%E7%8E%B0-Trie-%E5%89%8D%E7%BC%80%E6%A0%91"><span class="nav-number">3.1.</span> <span class="nav-text">208. 实现 Trie (前缀树)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#211-%E6%B7%BB%E5%8A%A0%E4%B8%8E%E6%90%9C%E7%B4%A2%E5%8D%95%E8%AF%8D-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%AE%BE%E8%AE%A1"><span class="nav-number">3.2.</span> <span class="nav-text">211. 添加与搜索单词 - 数据结构设计</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#677-%E9%94%AE%E5%80%BC%E6%98%A0%E5%B0%84"><span class="nav-number">3.3.</span> <span class="nav-text">677. 键值映射</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#820-%E5%8D%95%E8%AF%8D%E7%9A%84%E5%8E%8B%E7%BC%A9%E7%BC%96%E7%A0%81"><span class="nav-number">3.4.</span> <span class="nav-text">820. 单词的压缩编码</span></a></li></ol></li></ol>
    </div>
</div>
        </aside>
    

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fas fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fas fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fas fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>



<script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/utils.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/main.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/header-shrink.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/back2top.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/dark-light-toggle.js"></script>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/local-search.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/code-copy.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/lazyload.js"></script>


<div class="post-scripts pjax">
    
        <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/left-side-toggle.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/anime.min.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/toc.js"></script>
    
</div>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/pjax.min.js"></script>
<script>
    window.addEventListener('DOMContentLoaded', () => {
        window.pjax = new Pjax({
            selectors: [
                'head title',
                '.page-container',
                '.pjax'
            ],
            history: true,
            debug: false,
            cacheBust: false,
            timeout: 0,
            analytics: false,
            currentUrlFullReload: false,
            scrollRestoration: false,
            // scrollTo: true,
        });

        document.addEventListener('pjax:send', () => {
            KEEP.utils.pjaxProgressBarStart();
        });

        document.addEventListener('pjax:complete', () => {
            KEEP.utils.pjaxProgressBarEnd();
            window.pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
            KEEP.refresh();
        });
    });
</script>



<script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.x/lib/L2Dwidget.min.js"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"https://cdn.jsdelivr.net/npm/live2d-widget-model-hijiki@1.0.5/assets/hijiki.model.json"},"display":{"superSample":2,"width":160,"height":320,"position":"right","hOffset":0,"vOffset":-70},"mobile":{"show":false,"scale":0.2},"log":false});</script></body>
</html>
